package acm.蓝桥22;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

/**
 * https://www.luogu.com.cn/problem/solution/P8794 题意： 无向边权图
 * 边权每次将某个点的所有边权--，从0号点到N-1号点，最多减到L。问至少多少天 这个题容易想到弗洛伊德，求任意点到任意点的最短路。
 * 关键是不可能每次都跑一次弗洛伊德。 所以还要想到天数可以二分
 * 这题不会，好麻烦
 */
public class B_环境治理 {
	static int maxn = 100, maxv = 100001;
	static long[][] map = new long[maxn][maxn];
	static long[][] low = new long[maxn][maxn];
	static long[][] floyd = new long[maxn][maxn];
	static int n;
	static int q;

	public static void main(String[] args) {
		Reader2 sc = new Reader2();
		n = sc.nextInt();
		q = sc.nextInt();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				low[i][j] = sc.nextInt();
			}
		}
		long res = find();
		System.out.println(res);
	}

	public static long find() {
		long l = 0, r = Integer.MAX_VALUE;
		while (l <= r) {
			long m = l + (r - l >> 1);
			if (check(m)) {
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return l > Integer.MAX_VALUE ? -1 : l;
	}

	public static boolean check(long m) {
		long[][] f = floyd(m);
		long p = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				p += floyd[i][j];
			}
		}
		return p <= q;
	}

	/**
	 * 经过k天之后，弗洛伊德的结果
	 * 
	 * @param k
	 * @return
	 */
	public static long[][] floyd(long k) {
		floyd = map.clone();
		long cnt = k / n * 2;
		long mod = k % n;
		for (int i = 0; i < n && i < mod; i++) {
			for (int j = 0; j < n; j++) {
				// 清理过了几轮
				floyd[i][j] = Math.max(map[i][j] - cnt - 1, low[i][j]);
				floyd[j][i] = Math.max(map[j][i] - cnt - 1, low[j][i]);
			}
		}
		for (int t = 0; t < n; t++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					// 因为每个点都任一点都有边，所以无需判无边的情况
					floyd[i][j] = Math.min(floyd[i][j], floyd[i][t] + floyd[t][j]);
				}
			}
		}
		return floyd;
	}

	static class Reader2 {
		static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

		public Reader2(Object... o) {
		}

		public int nextInt() {
			try {
				in.nextToken();
			} catch (Exception ignored) {
			}
			return (int) in.nval;
		}
	}

}
